In [1]:

    

def half(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total / 2
    nums = sorted(nums, reverse = True)
    def work(level, s1, s2):
        if s1 < 0 or s2 < 0:
            return False
        x = nums[level]
        if s1 - x == 0 or s2 - x == 0:
            return True
        return ((x < s1) and work(level + 1, s1 - x, s2)) or ((x < s2) and work(level + 1, s1, s2 - x))
    return work(1, target - nums[0], target)


    

In [2]:

    

test = [1] * 99 + [100]
half(test)


    

    
Out[2]:





False

In [3]:

    

test = [1] * 99 + [95, 97]
half(test)


    

    
Out[3]:





False

In [4]:

    

half([1, 5, 5, 2, 9])


    

    
Out[4]:





True

In [5]:

    

def partition(nums, k = 2):
    total = sum(nums)
    if total % k:
        return False
    target = total // k
    nums = sorted(nums, reverse = True)
    n = len(nums)
    result = [target - nums[0]] + [target] * (k - 1)
    def work(level):
        if level == n:
            return True
        x = nums[level]
        for idx in range(k):
            s = result[idx]
            if s < 0:
                return False
            if s >= x:
                result[idx] = s - x
                if work(level + 1):
                    return True
                result[idx] = s
        return False
    return work(1)


    

In [6]:

    

partition([4, 3, 2, 3, 5, 2, 1], 4)


    

    
Out[6]:





True

In [7]:

    

def f(nums, k = 2):
    total = sum(nums)
    if total % k:
        return False
    target = total // k
    n = len(nums)
    selected = [False] * n
    def work(nk, agg, idx):
        if nk == 1:
            return True
        if agg == target:
            return work(nk - 1, 0, 0)
        for i in range(idx, n):
            if not selected[i] and agg + nums[i] <= target:
                selected[i] = True
                if work(nk, agg + nums[i], idx + 1):
                    return True
                selected[i] = False
        return False
    return work(k, 0, 0)


    

In [8]:

    

f([4, 3, 2, 3, 5, 2, 1], 4)


    

    
Out[8]:





True

In [12]:

    

test = [4, 3, 2, 3, 5, 2, 5]
print(f(test, 4), partition(test, 4))


    

    




False False

In [10]:

    

%timeit f(test, 4)


    

    




82.1 µs ± 583 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [11]:

    

%timeit partition(test, 4)


    

    




24.1 µs ± 599 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [13]:

    

test = [4, 3, 2, 3, 5, 2, 1]
print(f(test, 4), partition(test, 4))


    

    




True True

In [14]:

    

%timeit f(test, 4)


    

    




6.22 µs ± 74.4 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [15]:

    

%timeit partition(test, 4)


    

    




6.39 µs ± 132 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [ ]: